import java.util.*;

public class MyBinaryTree {
    private boolean isSameNode(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        if (left != null && right == null || left == null && right != null) return false;
        if (left.val != right.val) return false;
        return isSameNode(left.left,right.right) && isSameNode(left.right,right.left);
    }
    public boolean isSymmetric(TreeNode root) {
        return isSameNode(root.left,root.right);
    }
    public static int h = 0;
    public static TreeNode creatTree(String s) {
        char ch = s.charAt(h);
        h++;
        if (ch == '#') return null;
        TreeNode root = new TreeNode(ch);
        root.left = creatTree(s);
        root.right = creatTree(s);
        return root;
    }

    public static void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                list.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }
    StringBuilder sb = new StringBuilder();
    void dfs(TreeNode node) {
        if (node == null) return;
        sb.append(node.val);

        if (node.left != null || node.right != null) {
            sb.append("(");
            dfs(node.left);
            sb.append(")");
        }

        if (node.right != null) {
            sb.append("(");
            dfs(node.right);
            sb.append(")");
        }
    }
    public String tree2str(TreeNode root) {
        dfs(root);
        return sb.toString();
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null || !stack.empty()){
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                prev = top;
                stack.pop();
                list.add(top.val);
            } else {
                cur = top.right;
            }
        }
        return list;
    }
    public static int i = 0;
    public static int searchIdx(int pre,int[] inorder,int left,int right){
        if (right < left) return -1;
        for (int j = left; j <= right; j++){
            if (inorder[j] == pre) {
                return j;
            }
        }
        return -1;
    }
    public static TreeNode myBuildTree(int[] preorder, int[] inorder, int left, int right) {
        TreeNode root;
        if (i >= preorder.length) return null;
        int idx = searchIdx(preorder[i],inorder,left,right);
        if (idx != -1) {
            i++;
            root = new TreeNode(inorder[idx]);
        } else {
            return null;
        }
        System.out.println(root.val);
        root.left = myBuildTree(preorder,inorder,left,idx-1);
        root.right = myBuildTree(preorder,inorder,idx+1,right);
        return root;
    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        return myBuildTree(preorder,inorder,0,preorder.length - 1);
    }

    public static void main(String[] args) {
        /*PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        Scanner sc = new Scanner(System.in);*/
        int[] pre = {3,9,20,15,7};
        int[] in = {9,3,15,20,7};
        buildTree(pre,in);
    }
}
